Ramsey Number

定义 Definition

Ramsey number（拉姆齐数）是组合数学/图论中的一个概念：最小的整数 \(R(s,t)\)，使得任意把完全图 \(K_{R(s,t)}\) 的边染成两种颜色（常说红/蓝），都必然出现一个红色的 \(K_s\) 或一个蓝色的 \(K_t\)。它表达了“足够大时，混乱中必然出现结构”的思想。（也有多色与超图等推广定义。）

例句 Examples

The Ramsey number \(R(3,3)\) equals 6.
拉姆齐数 \(R(3,3)\) 等于 6。

In Ramsey theory, bounding Ramsey numbers is notoriously difficult, and only a few exact values are known.
在拉姆齐理论中，给拉姆齐数做上下界非常困难，已知的精确值只有少数几个。

发音 Pronunciation (IPA)

/ˈræmzi ˈnʌmbər/

词源 Etymology

“Ramsey number”得名于英国数学家 Frank P. Ramsey（弗兰克·拉姆齐）。他在 1930 年的论文中提出了后来被称为“拉姆齐理论”的核心思想：在足够大的结构中，总能找到某种有序子结构；“number”在此指与该性质相关的最小临界规模。

相关词 Related Words

• Ramsey Theory
• Graph
• Complete Graph
• Clique
• Edge Coloring
• Combinatorics
• Pigeonhole Principle
• Extremal Graph Theory

文献与作品 Literary Works

• Frank P. Ramsey, “On a Problem of Formal Logic” (1930)（奠基性论文，思想源头）
• Ronald L. Graham, Bruce L. Rothschild, Joel H. Spencer, **Ramsey Theory**（经典专著，系统讨论拉姆齐数与相关结果）
• Paul Erdős, Joel H. Spencer, **Probabilistic Methods in Combinatorics**（含用概率方法给拉姆齐数做界的典型思路）
• Martin J. Erickson（编）, The Cambridge Companion to Ramsey Theory 等相关综述性著作（常讨论拉姆齐数的已知值与界）